/*
 * Copyright (c) 2007, 2012, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */
/**
 * <h1>Code Eviction in the Maxine VM</h1>
 * Maxine features no interpreter but instead employs only <a href="http://en.wikipedia.org/wiki/Just-in-time_compilation">just-in-time compilation</a>.
 * This implies considerable amounts of machine code are created in the course of executing an application. Machine code can become outdated:
 * methods may, after their first execution, later be recompiled by the optimizing compiler, and static class initializers are even executed only once.
 * To address the memory requirement issue, <i>code eviction</i> was introduced to Maxine in Fall 2011 for baseline code,
 * that is, machine code generated by the <a href="https://wikis.oracle.com/display/MaxineVM/T1X">T1X compiler</a>.
 *
 * <h2>Baseline Code Cache Management</h2>
 * Prior to the introduction of code eviction, Maxine featured two <i>unmanaged</i> code caches, that is, memory areas where machine code is placed.
 * The boot code region contains all machine code belonging to the VM, it is filled during
 * <a href="https://wikis.oracle.com/display/MaxineVM/Boot+Image">boot image building</a>.
 * The run-time code region was the one where all code generated by either of the JIT compilers went. After introducing code eviction,
 * the boot code and run-time code regions still exist and are unmanaged, but the latter now only contains code generated by the optimizing compiler.
 * One managed code region for baseline code was added. It adopts a <i>semi-space</i> scheme as known from garbage collection.
 * The most important benefit of this scheme is that it implicitly compacts memory upon collection, so that bump-pointer allocation can be applied.
 * The {@linkplain com.sun.max.vm.code.SemiSpaceCodeRegion semi-space code region} <i>to-space</i> is where newly allocated code is placed
 * (and where code surviving an eviction cycle is moved); its <i>from-space</i> is where code subject to eviction is found.
 *
 * <h2>Code Eviction Workflow</h2>
 * An <i>eviction cycle</i> is triggered when the VM's attempt to allocate space in the baseline code region fails.
 * If that happens, all threads are suspended (eviction is a {@link com.sun.max.vm.runtime.VmOperation stop-the-world VM Operation}).
 * The workflow is controlled from the {@link com.sun.max.vm.code.CodeEviction#doIt()} method, and
 * proceeds in the following steps.
 *
 * <h3>Identify Survivors</h3>
 * The eviction logic needs to know which machine code survives the eviction cycle. This takes place in two steps:
 * <ol>
 * <li>walk all suspended threads' call stacks and mark the baseline methods currently executing as <i>live</i>.
 * Likewise, their direct callees, if they are baseline methods as well, are marked as live.
 * This ensures that code of methods currently being run in any of the threads will not be evicted, and also that code of methods
 * that are very likely to be invoked again survives.</li>
 * <li>iterate over the current to-space and mark methods as live that need to be protected from eviction for other reasons than
 * being executed or likely to be invoked; namely, methods that
 * <ul>
 * <li>have just been compiled but were not yet placed in the baseline code cache (such methods are typically the reason for an eviction
 * cycle to be triggered in the first place)</li>
 * <li>have an invocation counter within optimization threshold and/or a type profile (such methods might soon be recompiled by the
 * optimizing compiler, and the profile information gathered for them should not be lost)</li>
 * </ul>
 * </li>
 * </ol>
 *
 * <h3>Invalidate Non-live Methods</h3>
 * Invalidation takes place in three steps:
 * <ol>
 * <li>the machine code of non-live methods in the baseline code region is overwritten with trap instructions.
 * This is not strictly necessary but greatly helps in debugging</li>
 * <li>all entries in <i>vtables</i> and <i>itables</i> pointing to these methods are invalidated by letting them point to the respective
 * <a href="https://wikis.oracle.com/display/MaxineVM/Glossary">trampolines</a> again.
 * This is facilitated by iterating over the hubs of all loaded classes</li>
 * <li>all direct calls to non-live methods are invalidated by letting them reference trampolines again as well.
 * This implies iterating over all machine code in the three different code regions and checking direct call sites.
 * Direct calls from the boot code region to baseline code are rare, so there is an optimization in place that collects all
 * such calls (they are established at run-time) and thereby avoids iterating over the entire boot code region</li>
 * </ol>
 *
 * <h3>Move Live Methods</h3>
 * This is the step where semi-space functionality is actually applied.
 * This affects methods that have not been wiped in the previous step. In particular, this involves the following steps for
 * each live method:
 * <ol>
 * <li>Invalidate <i>vtable</i> and <i>itable</i> entries.</li>
 * <li>Copy the method's entire bytes (code and literals arrays) over to to-space.</li>
 * <li>Wipe the machine code and literal arrays as described above.</li>
 * <li>Memoise the old start of the method in from-space, and set new values for its start and end in to-space.</li>
 * <li>Compute and set new values for the code and literals arrays and for the {@linkplain com.sun.max.vm.compiler.target.TargetMethod#codeStart codeStart}
 * pointer.</li>
 * <li>Advance the to-space allocation mark by the method's size.</li>
 * <li>Fix direct calls in and to moved code.<br>
 * Direct call sites are relative calls. Hence, <b>all</b> direct calls <b>in</b> moved code have to be adjusted. This is
 * achieved by iterating over all baseline methods (at this point, only methods surviving eviction are affected) and fixing all
 * direct call sites contained therein.<br>
 * Also, direct calls <b>to</b> moved code have to be adjusted. This is achieved by iterating over the optimized and boot code
 * regions and fixing all direct calls to moved code.</li>
 * <li>Compact the baseline code region's {@linkplain com.sun.max.vm.code.SemiSpaceCodeRegion#targetMethods target methods array}<br>
 * by removing entries for wiped (stale) methods.</li>
 * <li>Fix return addresses on call stacks, and code pointers in local variables.<br>
 * Walk all threads' call stacks once more and fix return addresses that point to moved code. Likewise, fix pointers to machine
 * code held in {@link com.sun.max.unsafe.CodePointer}s in the frames of the methods. This logic makes use of the saved old code start of moved
 * methods.</li>
 * </ol>
 * <p>
 * <h2>Tracing and Logging</h2>
 * The eviction algorithm contains copious logging capability using the {@link com.sun.max.vm.log.VMLogger} mechanism.
 * There are two distinct capabilities; <i>logging</i> the flow of the algorithm and <i>dumping</i> pertinent state
 * of the VM before and after the algorithm executes. Dumping is very verbose and does not place data in the
 * {@link com.sun.max.vm.log.VMLog VM log buffer}. However, it is defined as an logging operation so that it can be
 * enabled using a consistent mechanism.
 * <p>
 * The loggable operations are separated into four areas, statistics, algorithmic details, code moving and dumping,
 * with the operations names prefixed by {@code Stats_}, {@code Details_}, {@code Move_} and {@code Dump}, respectively.
 * The VM option {@code -XX:+LogCodeEviction} is used to enable logging, with tracing to the
 * log file enabled with {@code -XX:+TraceCodeEviction}. The options {@code -XX:+LogCodeEvictionInclude} and
 * {@code -XX:+LogCodeEvictionExclude} can be used to fine control which options are logged/traced.
 * The operation prefixes can be used in regular expressions to enable all operations in a particular area, for example:
 * {@code -XX:+LogCodeEvictionExclude=Stats_.*}. Note that dumping must be explicitly enabled with {@code -XX:+LogCodeEvictionInclude=Dump}
 *
 */
package com.sun.max.vm.code;

